package offer.day24;

public class No39MoreThanHalfNum_ArrayFeature {
    /*
     * 面试题39：数组中出现次数超过一半的数字
     * 题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
     * 例如：输入一个长度为9的数组{1，2，3，2，2，2，5，4，2}.
     * 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2
     *
     *
     * 思路：根据数组特点找出时间复杂度为O(n)的算法
     * 定义两个变量：一个用于记录数字  一个用于记录数字出现的次数
     * 首次访问该数字时，次数设置为1，访问之后的元素，相等，则加1；不等，则减1；
     * 若次数等于零，则开始记录下一个数字
     * 其中因为重复超过数组的一半，所以该数字应该是最后一个次数被设置为1的值
     *
     *
     *
     * */
    //int flag = 0;
    //标志位（当number=0时）  ：若flag为0  表示数组不为空   若flag为1  表示数组为空

    public static void main(String[] args) {
        No39MoreThanHalfNum_ArrayFeature m = new No39MoreThanHalfNum_ArrayFeature();
        int[] array = {1,2,3,2,2,2,5,4,2};
        System.out.println("数组中超过一半的数字是："+m.MoreThanHalfNum_Solution(array));
    }

    private int MoreThanHalfNum_Solution(int[] array) {
        if(array==null||array.length==0){
            return 0;
        }
        int result=array[0];
        int times=1;
        for(int i=1;i< array.length;i++){
            if(times==0){
                result=array[i];
                times=1;
            }else if(array[i]==times){
                times++;
            }else {
                times--;
            }
        }
        if(checkMoreThanHalf(array,result))

            return result;

        return 0;
    }

    private boolean checkMoreThanHalf(int[] array, int result) {
        int count=0;
        for(int i=0;i<array.length;i++){
            if(array[i]==result){
                count++;
            }
        }
        return count>array.length/2;
    }
}
